;############################################################################ 

; Инициализация глобальных переменных
; Аргументы:
;			нет
; Возвращаемое значение:
;			code - все байты обнулены (256 * 4 = 1024 байт) 
;			num_bit - все байты обнулены (256 байт)
;			head_list - все байты обнулены (4-е байта)
;			end_array - все байты обнулены (4-е байта)
;			begin_allocated_memory - все байты обнулены (4-е байта)
;			root - все байты обнулены (4-е байта)
;			tree_size - все байты обнулены (2 байта)

init_global_variable:

	mov [head_list],dword 0
	mov [end_array],dword 0
	mov [begin_allocated_memory],dword 0
	mov [root],dword 0
	mov [tree_size],word 0

	mov ecx,100h
	mov esi,code
	mov edi,num_bit

	IGV_next_elem:
		mov [esi],dword 0
		mov [edi],byte 0
		add esi,4
		inc edi
	loop IGV_next_elem

	call get_seek_set
	mov [SEEK_SET],eax

	ret

;############################################################################ 

; Создание отсортированного по возрастанию ключей связного списка стоков дерева Хаффмана
; Ключ - количество вхождений символа в исходный файл
; Аргументы:
;			code - массив количеств вхождений каждого символа в исходный файл (256 элементов по 4-е байта)
;			[tree_size] - число различных символов, входящий в файл
; Возвращаемые значения:
;			al - результат выполнения (0 - успех, > 0 - неудача)
;			[head_list] - адрес вершины списка
;			[end_array] - адрес конца массива списков + 1
;			begin_allocated_memory - указатель на начало области памяти, выделенной под дерево

create_list:

	; Сохраняем данные о стеке
	push ebp
	mov ebp,esp

	; Поместим в eax количество стоков будущего дерева (количество различных символов, входящих в файл)
	movzx eax,word [tree_size]

	; Проверим, пуст ли входной файл
	test eax,eax
	jnz CL_list_not_null
		; Ошибка, если входной файл пуст
		mov al,CL_null_list
		jmp CL_end

	CL_list_not_null:

	; Сохраняем размер массива стоков (для последующей сортировки)
	push ax

	; Поместим в ax (количество узлов в дереве + 1)
	; количество_узлов_в_дереве = ax * 2 - 1
	; В том случае, если в файле всего лишь один символ (возможно, встречающийся
	; несколько раз), нам потребуется элемент - граница
	shl ax,1
	; Сохраняем (количество узлов дерева + 1)
	mov [tree_size],ax
	; В eax теперь размер дерева: (ax * elem_size) байт
	mov bx,elem_size
	mul bx

	; Выделить память для дерева
	push eax
	call malloc
	test eax,eax
	jnz CL_malloc_no_error
		mov al,CL_malloc_error
		jmp CL_end

	CL_malloc_no_error:

	; Список стоков дерева будет занимать часть области, выделенной под дерево, начиная с begin_allocated_memory
	; (head_list != begin_allocated_memory - в общем случае)

	; Сохраняем указатель на начало области памяти, выделенной под дерево
	mov [begin_allocated_memory],eax

	; Инициализируем указатель на начало списка
	mov [head_list],eax

	; Разместить массив стоков в области памяти, начиная с head_list

	; ebx адресует следующий доступный для записи элемент в массиве элементов дерева
	mov ebx,eax
	; esi адресует массив количеств вхождений каждого символа
	mov esi,code
	; ecx - количество символов в code
	mov ecx,100h

	push ebp
	xor ebp,ebp
	CL_put_new_elem_in_array:
		; Если текущий символ входит в файл хотя бы один раз... 
		cmp [esi],ebp
		; ... то поместить его в массив стоков
		jz CL_symb_not_found_in_file
			; Вычисляем код символа как  (100h - cx)
			mov dx,cx
			mov ax,100h
			sub ax,dx
			mov [ebx + elem_code_dis],al
			; Сыновей у стока нет
			mov [ebx + elem_right_dis],ebp
			mov [ebx + elem_left_dis],ebp
			; Данные о предыдущем/последующем элементах списка будут занесены позже
			; Сохраняем количество вхождений символа
			mov edi,[esi]
			mov [ebx + elem_num_dis],edi
			; Переходим к следующему доступному элементу в массиве элементов дерева
			add ebx,elem_size
		CL_symb_not_found_in_file:
		; Переходим к следующему символу
		add esi,4h
	loop CL_put_new_elem_in_array
	pop ebp
	
	; Сохраним указатель на конец массива элементов. Это указатель будет использоваться при размещении
	; новых узлов дерева
	mov [end_array],ebx
	; Метка окончания массива стоков - 0 в поле elem_num_dis
	mov [ebx + elem_num_dis],dword 0

	; Отсортировать массив стоков
	mov esi,[head_list]
	mov edi,ebx
	; Адрес начала массива - esi, адрес конца массива - edi
	call sort

	; Составить список стоков на основе массива стоков
	; (инициализировать адреса предыдущего/следующего элементов для каждого элемента)

	; ebx адресует текущий обрабатываемый элемент списка
	mov ebx,[head_list]
	; edi адресует следующий элемент
	mov edi,ebx
	add edi,elem_size

	CL_next_list_elem:
		; Инициализируем поле "следующий элемент в списке"
		mov [ebx + elem_next_dis],edi
		; ebx = следующий элемент
		mov ebx,edi
		; edi = следующий за текущим следующим элементом
		add edi,elem_size
		; Проверяем, не завершился ли массив (поле "количество вхождений" установлено в 0)
		mov eax,[ebx + elem_num_dis]
		test eax,eax
	jnz CL_next_list_elem

	; Последний элемент списка в поле "следующий элемент" имеет ноль
	xor eax,eax
	sub ebx,elem_size
	mov [ebx + elem_next_dis],eax

	; Возращаем ноль в случае удачного выполнения подпрограммы

	CL_end:
		
	; Восстанавливаем стек
	mov esp,ebp
	pop ebp

	ret

;############################################################################ 

; Создание дерева Хаффмана (двоичное полное дерево; размер (tree_size * elem_size) байт;
; корень - root; элемент - elem_size байт; стоки соответствуют символам, встретившимся во
; входной последовательности)
; Аргументы:
;			[head_list] - адрес первого элемента отсортированного списка стоков дерева
;			[end_array] - адрес последнего элемента в массиве стоков
; Возвращаемое значение:
;			al - результат выполнения (0 - успех, > 0 - неудача)
;			[root] - адрес корня дерева

create_tree:
	
	; Сохраняем данные о стеке
	push ebp
	mov ebp,esp

	; esi указывает на текущую вершину списка
	mov esi,[head_list]
	; edi указывает на свободное пространство области памяти, выделенной под дерево
	; (по адресу из edi будет создаваться следующий узел дерева)
	mov edi,[end_array]
	
	; Если список пуст - завершить функцию
	cmp esi,edi
	jz CT_find_root_1

	CT_next:
		; Переходим к следующему (после вершины) элементу
		mov ebx,[esi + elem_next_dis]

		; Если такового нет - то текущая вершина есть корень дерева
		test ebx,ebx
		jz CT_find_root_2

			; Если в текущем списке как минимум два элемента - создать новый узел дерева, левым и правым сыновьями
			; которого будут соответственно первый и второй элементы списка, а количество вхождений - сумма количеств
			; вхождений левого и правого сыновей
			mov [edi + elem_left_dis],esi
			mov [edi + elem_right_dis],ebx
			mov [edi + elem_code_dis],byte 0
			mov eax,[esi + elem_num_dis]
			mov edx,[ebx + elem_num_dis]
			add eax,edx
			mov [edi + elem_num_dis],eax

			; Перейдем к новому началу списка, убрав первые два элемента из текущего
			mov esi,[ebx + elem_next_dis]
			test esi,esi
			; Если список кончился - то созданный только что узел дерева и будет корнем
			jz CT_find_root_3
				; Иначе вставим созданный узел в отсортированный список
				call insert_in_list

	jmp short CT_next

	CT_find_root_1:
		; Список пуст => указатель на корень дерева будет установлен в 0
		mov [root],dword 0
		jmp short CT_end
	CT_find_root_2:
		; Список состоит из одного элемента => корень дерева есть первый элемент списка
		mov [root],esi
		jmp short CT_end
	CT_find_root_3:
		; Список состоит из нескольких элементов и был создан последний узел дерева =>
		; последний созданный узел дерева есть корень дерева
		mov [root],edi

	CT_end:

	xor eax,eax

	; Восстанавливаем стек
	mov esp,ebp
	pop ebp

	ret

;############################################################################ 

; Включение элемента в отсортированный список
;
; Аргументы:
;			esi - адрес первого элемента списка
;			edi - адрес включаемого элемента
; Возвращаемое значение:
;			edi - адрес конца массива элементов списка + 1
; Комментарий:
;			элемент необходимо включить перед элементом, меньшим или равным включаемому
;			ключ - количество вхождений (адрес + elem_num_dis)

insert_in_list:

	; Сохраняем данные о стеке
	push ebp
	mov ebp,esp

	; Будем использовать локальную переменную на стеке для хранения адреса начала списка
	push esi
	; В ecx ключ вставляемого элемента
	mov ecx,[edi + elem_num_dis]
	; Адрес текущего предыдущего элемента = 0 (начало списка)
	xor ebx,ebx

	; Последовательный поиск в списке элемента, меньшего или равного включаемому
	IIL_next:
		; Ключ очередного элемента -> eax
		mov eax,[esi + elem_num_dis]
		cmp eax,ecx
		; Если очередной элемент меньше - продолжить поиск
		jb IIL_jump_to_next
			; Иначе - вставить элемент в список
			mov [edi + elem_next_dis],esi
			; Корректным образом проверим, является ли вставляемый элемент первым в списке
			test ebx,ebx
			jz IIL_first_in_list
				; Если нет - то существует элемент, ссылающийся на вставляемый как на следующий
				mov [ebx + elem_next_dis],edi
				jmp short IIL_first_end_if
			IIL_first_in_list:
				; Иначе - считаем вставляемый элемент первым
				mov [esp],edi
			IIL_first_end_if:
			; После вставки - выходим
			jmp short IIL_end
		IIL_jump_to_next:
		mov ebx,esi
		mov esi,[esi + elem_next_dis]
		; Завершить цикл, если список кончился
		test esi,esi
	jnz IIL_next

	; Вставим элемент в конец списка (т.о. test esi,esi установил ZF => esi == 0)
	mov [ebx + elem_next_dis],edi
	mov [edi + elem_next_dis],esi

	IIL_end:

	; Перейти к следующему незанятому элементу массива
	add edi,elem_size

	; Адрес начала списка выбрать из стека
	pop esi

	; Восстанавливаем стек
	mov esp,ebp
	pop ebp

	ret

;############################################################################ 

; Сортировка последовательности (массив стоков дерева)
; по возрастанию ключа
; Аргументы:
;			esi - адрес первого элемента последовательности
;			edi - адрес последнего элемента последовательности + 1
; Возвращаемое значение:
;			нет

sort:

	; Размер элемента последовательности - elem_size
	; Смещение ключа относительно адреса элемента - elem_num_dis
	; Размер последовательности: ([head_list] - ebx) / elem_size
	; Максимальное количество элементов в последовательности - 256

	; Используется алгоритм быстрой сортировки

	; esi и edi адресуют ключи (первого и (последний + 1)-го элемента)
	add esi,elem_num_dis
	add edi,elem_num_dis

	; Вложенная подпрограмма для рекурсивного вызова
	S_recursion:

	; Сохраняем данные о стеке
	push ebp
	mov ebp,esp

	; Будем группировать элементы последовательности относительно срединного элемента,
	; для чего вычислим значение ключа срединного элемента
	xor edx,edx
	mov cx,elem_size
	mov eax,edi
	sub eax,esi
	; (((eax / cx) / 2) * cx) != (eax / 2), поскольку деление на 2 -
	; целочисленное с округлением в меньшую сторону
	div cx
	shr eax,1
	mul cx
	; Как показала практика, следующие две инструкции в среднем дают значительный прирост
	; производительности по сравнению с "mov eax,[esi + eax]"
	mov ebx,eax
	mov eax,[esi + ebx]
	; В eax теперь ключ срединного элемента
	push eax

	; Сохраним смещенный границы последовательности
	mov ecx,esi
	mov edx,edi
	; edi теперь адресует ключ последнего элемента последовательности
	sub edi,elem_size

	; Главный цикл выполняется до тех пор, пока левая и правая границы не встретятся
	; Встреча означает, что последовательность разделена на две части относительно значения eax
	S_main_loop_begin:
	cmp esi,edi
	jg S_end_main_loop

		; Ищем следующий элемент слева, ключ которого будет больше значения eax
		S_begin_first_loop:
		cmp [esi],eax
		jge S_end_first_loop
			add esi,elem_size
		jmp short S_begin_first_loop
		S_end_first_loop:

		; Ищем следующий элемент справа, ключ которого будет меньше значения eax
		S_begin_second_loop:
		cmp [edi],eax
		jng S_end_second_loop
			sub edi,elem_size
		jmp short S_begin_second_loop
		S_end_second_loop:

		; В том случае, если справа и слева есть элементы, ключи которых больше и меньше
		; значения eax соответственно, то поменяем эти элементы
		cmp esi,edi
		jg S_endif_1
			; Меняем только поля "код символа" и "количество вхождений" элемента
			; Остальные поля нас не интересуют, так как ни дерево, ни список пока еще не
			; сформированы
			mov bl,[esi - elem_num_dis + elem_code_dis]
			mov bh,[edi - elem_num_dis + elem_code_dis]
			mov [esi - elem_num_dis + elem_code_dis],bh
			mov [edi - elem_num_dis + elem_code_dis],bl
			mov eax,[esi]
			mov ebx,[edi]
			mov [esi],ebx
			mov [edi],eax
			mov eax,[esp]

			add esi,elem_size
			sub edi,elem_size
		S_endif_1:

	jmp short S_main_loop_begin
	S_end_main_loop:
	
	; Если слева от esi есть последовательность - сортировать ее
	cmp esi,edx
	jge S_endif_2
		push esi
		push edi
		push ecx

		; Сортировать последовательность от esi до правой границы
		; родительской последовательности
		mov edi,edx
		call S_recursion

		pop ecx
		pop edi
		pop esi
	S_endif_2:

	; Если слева от edi есть последовательность - сортировать ее
	cmp edi,ecx
	jng S_endif_3
		
		; Сортировать последовательность от левой границы родительской
		; последовательности до edi
		mov esi,ecx
		add edi,elem_size
		call S_recursion

	S_endif_3:

	; Восстанавливаем стек
	mov esp,ebp
	pop ebp

	ret

;############################################################################ 

; Создание массивов кодов (Хаффмана)
; Аргументы:
;			[root] - адрес вершины дерева Хаффмана
; Возвращаемое значение:
;			al - результат выполнения (0 - успех, > 0 - неудача)
;			code - массив кодов Хаффмана символов (256 элементов по 4-е байта)
;			num_bit - количество значащий бит в соответствующем коде code (256 элемента по 1 байту)

create_code_array:

	; Код Хаффмана суть есть закодированный маршрут. Переход по левому дереву кодируется нулем, переход по
	; правому - единицей. Старшие биты кода соответствуют ребрам, которые расположены ближе к корню дерева

	; eax - промежуточный код Хаффмана
	xor eax,eax
	; ebx - вершина текущего дерева
	mov ebx,[root]
	; cl - количество значащих битов в eax
	xor cl,cl

	; Задача - обойти дерево. Используем рекурсию. next_code - фактически, рекурсивно вызываемая функция
	CCA_next_code:
		
		; Сохраняем стек
		push ebp
		mov ebp,esp

		; Получаем адрес левого поддерева текущего корня
		mov edx,[ebx + elem_left_dis]
		
		; Проверяем на равенство адреса нулю (если равно - то корень суть есть сток)
		test edx,edx
		jz CCA_make_code
			; Корень не сток => существуют левое и правое поддерево
			
			; Формируем новый бит в коде Хаффмана
			shl eax,1
			; Количество битов теперь на единицу больше
			inc cl
			; И если произошло переполнение, то ошибка
			cmp cl,33
			jz CCA_us_end_next_code
				; Если переполнения не произошло, то рекурсивно вызовем next_code

				; Сохраним важные регистры (сохраним контекст текущего выполнения next_code)
				push ecx
				push eax
				push ebx
				
				; В качестве параметра передадим указатель на левое поддерево (оно станет корнем нового текущего дерева)
				mov ebx,edx
				; Вызов (для левого поддерева) (младший бит в eax = 0)
				call CCA_next_code
					; Проверка возвращаемого значения
					test al,al
					jnz CCA_us_end_next_code

				; Восстановим контекст
				pop ebx
				; В ebx - указатель на правое поддерево
				mov ebx,[ebx + elem_right_dis]
				pop eax
				; Младший бит eax теперь единица
				inc eax
				pop ecx
				; Вызов (для правого поддерева)
				call CCA_next_code
					; Проверка возвращаемого значения
					test al,al
					jnz CCA_us_end_next_code

				jmp short CCA_s_end_next_code
		
		CCA_make_code:
			; Если текущий корень - сток (т.к. указатели на его сыновей установлены в 0),
			; то занесем информацию о символе, описанном этим стоком, в массивы кодов Хаффмана

			; Проверяем, является ли ebx - корнем дерева. В этом случае в сжимаемом файле
			; присутствует только одно значение байта некоторое число раз
			; (дерево вырождается в корень без сыновей)
			cmp ebx,[root]
			jnz CCA_not_root
				inc cl
			CCA_not_root:

			; Вычислим смещение в массиве размерностей кодов Хаффмана (размер элементов в этом массиве равен байту =>
			; смещение равно коду символа)
			mov ebx,[ebx]
			; Запишем размер кода Хаффмана символа в битах в массив размерностей кодов Хаффмана
			mov [num_bit + ebx],cl

			; В массиве кодов Хаффмана храняться элементы по четыре байта => умножим смещение на 2
			shl ebx,2
			; Запишем код Хаффмана символа в массив кодов
			mov [code + ebx],eax

	CCA_s_end_next_code:
		; Удачное завершение next_code
		
		; Восстанавливаем стек
		mov esp,ebp
		pop ebp
		; Возвращаем ноль
		xor al,al
		ret

	CCA_us_end_next_code:
		; Неудачное завершение next_code

		; Причина неудачного завершения - переполнение кода Хаффмана (т.е. на некотором этапе cl стал равен 33-м))
		mov al,CCA_overflow_error

		; Восстанавливаем стек
		mov esp,ebp
		pop ebp

		ret

;############################################################################ 

